package org.lex.utils.tree;

import java.util.Iterator;

import org.lex.utils.collections.AggregativeIterator;


public abstract class Postorder implements Iterator<Node> {
	public static Postorder newInstance(Node root) {
		if (0 == root.getChildCount())
			return new TrivialPOT(root);
		else
			return new POT(root);
	}
}

/*
 * һ������µĺ������
 */
class POT extends Postorder {
	private boolean rootExplorered = false;
	private Iterator<Node> iter = null;
	private Node root = null;

	POT(Node root) {
		this.root = root;
		int childCount = root.getChildCount();
		Postorder[] array = new Postorder[childCount];
		for (int i = 0; i < childCount; i++) {
			Node child = root.getChildAt(i);
			Postorder pot = null;
			if (0 == child.getChildCount())
				pot = new TrivialPOT(child);
			else
				pot = new POT(child);
			array[i] = pot;
		}
		iter = new AggregativeIterator<Node>(array);
	}

	@Override
	public boolean hasNext() {
		if (iter.hasNext())
			return true;
		if (false == this.rootExplorered)
			return true;
		return false;
	}

	@Override
	public Node next() {
		if (iter.hasNext())
			return iter.next();
		if (false == this.rootExplorered) {
			this.rootExplorered = true;
			return root;
		}
		return null;
	}

	@Override
	public void remove() {
	}
}

/*
 * ����ֻ��һ���ڵ���������
 */
class TrivialPOT extends Postorder {
	private Node root = null;
	private boolean explorered = false;

	TrivialPOT(Node root) {
		this.root = root;
	}

	@Override
	public boolean hasNext() {
		return !explorered;
	}

	@Override
	public Node next() {
		this.explorered = true;
		return root;
	}

	@Override
	public void remove() {
	}
}
